#include <algorithm>
#include <string.h>
#include "mpi.h"

#include "tlg.h"
#include "log.h"
#include "stack.h"

#include <unistd.h> //sleep()
#include <cstdlib>  //exit()

#define CHECK_MSG_AMOUNT  400
#define MAX_WORK_REQUESTS 4

#define MSG_WORK_REQUEST 1000
#define MSG_WORK_SENT    1001
#define MSG_WORK_NOWORK  1002
#define MSG_TOKEN        1003
#define MSG_FINISH       1004

#define TKN_CAN_FINISH      0
#define TKN_CANNOT_FINISH   1

//NOTE praci ridi procesor 0, zmena by vedla k zesloziteni nekterych algoritmu, nemenit!
#define CEO_CPU             0
using namespace std;
int result;  // vysledna tloustka
bool isIddle = false;
bool tokenRunning = false;        // for CEO_CPU only.. 
bool workRequestResponsed = true; // if it's answered, we should ask next one


//------------------------------------------------------------------------------

/**
 * Zpracování příchozích zpráv procesoru (mimo zpráv poslaných na začátku při rozdělování práce)
 * vraci jestli se ma vyskocit
 */
void handleMessage(MPI_Status status, unsigned char *& buffer, int & buf_len){
	switch (status.MPI_TAG) {
		case MSG_WORK_REQUEST:
			if(!isIddle && sIsWorkToSend()){
				unsigned char *topStack;
				int topSize;
				sSplit(topStack, topSize);

				if(topStack == NULL){
					cout << "ERROR false work to send";
					exit(1);
				}

				MPI_Send(topStack, topSize, MPI_BYTE, status.MPI_SOURCE, MSG_WORK_SENT, MPI_COMM_WORLD);

				logstream << "NETWORK sent work: " << permutationToString(topStack, topSize) << " to cpu: " << (int)status.MPI_SOURCE;
				log(LOG_NET);

				delete[] topStack;
			} else {
				MPI_Send(NULL, 0, MPI_BYTE, status.MPI_SOURCE, MSG_WORK_NOWORK, MPI_COMM_WORLD);

				logstream << "NETWORK sent NoWork to: " << (int)status.MPI_SOURCE << " for stack[sTop]: " << (sIsEmpty() ? "empty" : permutationToString(stack[sTop], sizes[sTop]));
				log(LOG_NET);
			}
			break;

		case MSG_WORK_SENT:
			int len;
			MPI_Get_count(&status, MPI_BYTE, &len);
			sPush(buffer, len);
			logstream << "NETWORK got and pushed: " << permutationToString(buffer, len) << " from cpu: " << (int)status.MPI_SOURCE;
			log(LOG_NET);
			workRequestResponsed = true;
			break;

		case MSG_WORK_NOWORK:
			logstream << "NETWORK got: no work from cpu: " << (int)status.MPI_SOURCE;
			log(LOG_NET);
			workRequestResponsed = true;
			break;

		case MSG_TOKEN: // ===== ukoncovaci token, prijmout a nasledne preposlat - bily nebo cerny v zavislosti na stavu procesu
			if(my_rank == CEO_CPU) {
				if(buffer[0] == TKN_CAN_FINISH) {
					logstream << "NETWORK cpu:0 - token dosel, ukoncuju!";
					log(LOG_NET);

					for (int i = 1; i < cpu_count; i++) { // Send finnish!!
						MPI_Send(NULL, 0, MPI_BYTE, i, MSG_FINISH, MPI_COMM_WORLD);
					}

					// přijetí nejlepších výsledků binární redukcí od ostatních procesorů
					int recv_result; // obdržený nejlepší výsledek na předchozích procesorech
					MPI_Reduce(&result, &recv_result, 1, MPI_INT, MPI_MIN, CEO_CPU, MPI_COMM_WORLD); // NOTE musí zůstat stejné, jako v "case MSG_FINISH:" !!

					// ukončování činnost CEO_CPU // NOTE proč se vlastně volá MPI_Finalize na třech různých místech?
					cout << "==== " << "JSEM VELIKÁ NULA A NEJLEPŠÍ VÝSLEDEK JE: " << recv_result << " ====" << endl;
					
					isIddle = false;
				} else {
					logstream << "NETWORK: cpu " << my_rank << " got CANNOT FINISH TOKEN!";
					log(LOG_NET);

					tokenRunning = false;
				}
			} else {
				int next_cpu = (my_rank + 1) % cpu_count;
				unsigned char token = isIddle ? TKN_CAN_FINISH : TKN_CANNOT_FINISH;
				MPI_Send(&token, 1, MPI_BYTE, next_cpu, MSG_TOKEN, MPI_COMM_WORLD); // pošle TOKEN nasledujicimu jadru

				logstream << "NETWORK: cpu " << my_rank << " sent TOKEN:" << (int)token;
				log(LOG_NET);
			}
			break;

		case MSG_FINISH:
			logstream << "NETWORK cpu:" << my_rank << " got MSG_FINNIS, up to binary reduce result";
			log(LOG_NET);
			// odeslání (je aplikováno na všechny mimo CEO_CPU) nejlepšího výsledku procesoru CEO_CPU
			int recv_result; // obdržený nejlepší výsledek na předchozích procesorech, dále se nepoužívá
			MPI_Reduce(&result, &recv_result, 1, MPI_INT, MPI_MIN, CEO_CPU, MPI_COMM_WORLD); // NOTE musí zůstat stejné, jako v "case MSG_TOKEN:" !!
			isIddle = false; //vypade z isIddle smicky
			break;

		default: cout << "Error: Unknown message. Terminating." << endl;
			break;
	}
}

//------------------------------------------------------------------------------

void LoadAndDistributeData(char *input_file){
	if (my_rank == CEO_CPU) {
		// Vyplni promenne: n,t,k,M
		readMatrix(input_file);
	}

	MPI_Bcast (&n, 1, MPI_BYTE, CEO_CPU, MPI_COMM_WORLD);

	if (my_rank != CEO_CPU) {
		M = new unsigned char*[n];
		for (int i = 0; i < n; i++){
			M[i] = new unsigned char[n];
		}
	}
	

	result = n*n;  // vysledna tloustka, inicializuje se na horsi nez nejhorsi mozny pripad



	int buf_len = n * n + 2;
	unsigned char *buffer = new unsigned char[buf_len];

	if (my_rank == CEO_CPU) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				buffer[i*n + j] = M[i][j];
			}
		}
		buffer[buf_len - 2] = t;
		buffer[buf_len - 1] = k;
	}

	MPI_Bcast (buffer, buf_len, MPI_BYTE, CEO_CPU, MPI_COMM_WORLD); // rozeslání zadané matice sousednosti grafu

	if (my_rank != CEO_CPU) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				M[i][j] = buffer[i*n + j];
			}
		}
		t = buffer[buf_len - 2];
		k = buffer[buf_len - 1];
	}

	delete[] buffer;

	//printMatrix();
	//logstream << "cpu " << my_rank << ": n = " << (int)n << ", t = " << (int)t << ", k = " << (int)k;
	//log(LOG_DIST);
}

//------------------------------------------------------------------------------

void CreateAndSendInitialPermutations(){
	//  Určení vylikosti rozesílaných (a přijímaných) úloh
	int tsks = 1;    // počet všech zadání; hodnota jedna - první krok pro výpočet faktoriálu
	int tsks_per_me; // pocet permutaci pro toto jadro
	int perm_len;    // počet prvků permutace (délka zadání)

	for (perm_len = 1; tsks < cpu_count; tsks *= ++perm_len) { } // počet zadání na základě počtu procesorů
	tsks_per_me = tsks / cpu_count + ((tsks % cpu_count) > my_rank);

	logstream << "cpu_count: " << cpu_count << " tsks: " << tsks << " perm_len: " << perm_len;
	log(LOG_DIST);
	logstream << "my_rank: " << my_rank << " tsks_per_me: " << tsks_per_me;
	log(LOG_DIST);


	int stack_len = n*n;
	sInit(stack_len);


	if (my_rank == CEO_CPU) {
		unsigned char* perm = new unsigned char[perm_len];
		for (int i = 0; i < perm_len; i++) { perm[i] = i; }

		// Vlastni ulohy
		for (int i = 0; i < tsks_per_me; i++) { 
			unsigned char *own_perm = new unsigned char[perm_len];
			memcpy(own_perm, perm, perm_len);
			std::next_permutation(perm, perm + perm_len);

			sPush(own_perm, perm_len);

			logstream << "initpush: " << permutationToString(own_perm, perm_len);
			log(LOG_DIST);
		}

		//  Rozeslání úloh jinam
		for (int trgt = 1; trgt < cpu_count; trgt++) {
			int tsks_per_trgt_cpu = tsks / cpu_count + ((tsks % cpu_count) > trgt);

			int buf_len = tsks_per_trgt_cpu * perm_len;
			unsigned char *buffer = new unsigned char[buf_len];

			for (int i = 0; i < tsks_per_trgt_cpu; i++) {
				memcpy(buffer + i * perm_len, perm, perm_len);
				std::next_permutation(perm, perm + perm_len);
			}

			MPI_Send(buffer, buf_len, MPI_BYTE, trgt, 1, MPI_COMM_WORLD);

			delete[] buffer;
		}
		delete[] perm;
	} 

	//---------

	if( my_rank != CEO_CPU) {
		int buf_len = tsks_per_me * perm_len;
		unsigned char *buffer = new unsigned char[buf_len];

		MPI_Recv(buffer, buf_len, MPI_BYTE, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);

		for (int i = 0; i < tsks_per_me; i++) {
			unsigned char* own_perm = new unsigned char[perm_len];
			memcpy(own_perm, buffer + i * perm_len, perm_len);

			sPush(own_perm, perm_len);

			logstream << "initpush: " << permutationToString(own_perm, perm_len);
			log(LOG_DIST);
		}
		delete[] buffer;
	}
}

//------------------------------------------------------------------------------

bool CheckThisPermutationForMeDude( unsigned char *&p, int & len ){
/**
 * returns isTrivial
 */
	int tmpres = n*n;

	if (len == n) { // plna permutace, jsme v listu stromu permutaci
		if (p[0] < p[n - 1]) { // duplicitni permutace
			logstream << "duplicit:   " << permutationToString(p, len);
		} else { // neni duplicitni, takze ji zmerime a zkontrolujeme, jestli je lepsi nez dosud nalezeny vysledek
			tmpres = permutationThickness(p, len, result);
			if (tmpres < result) {
				result = tmpres;
				if (result == t) {
					logstream << "check fin:  " << permutationToString(p, len) << " result: " << tmpres << "/" << result << "TRIVIAL!!!!!!";
					log(LOG_STACK);
					return true;
				}
				logstream << "check fin:  " << permutationToString(p, len) << " result: " << tmpres << "/" << result << "goood";
			} else {
				logstream << "check fin:  " << permutationToString(p, len) << " result: " << tmpres << "/" << result << " baaad";
			}
		}
		log(LOG_STACK);
		delete[] p; //vsechny listy se mazou

	} else { // nejsme v listu stromu permutaci. merime jen pro prorezavani prebytecnych vetvi
		tmpres = permutationThickness(p, len, result);
		if (tmpres < result) { // pokud nejsme uz ted horsi nez dosud nejlepsi nalezena, pridame na zasobnik
			sPush(p, len);
			logstream << "check push: " << permutationToString(p, len) << " result: " << tmpres << "/" << result << " pushed";
		} else { // jinak rezeme prilis tluste vetve, muhehe 
			logstream << "check push: " << permutationToString(p, len) << " result: " << tmpres << "/" << result << " dead end";
			delete[] p;
		}
		log(LOG_STACK);
	}

	return false;
}

//------------------------------------------------------------------------------

void DoYoHearDaPhonaRingin(){
	int flag;
	MPI_Status status;
	MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);

	//cout << "cpu:" << my_rank << "NETWORK checking incomming message" << endl; 
	//logstream << "NETWORK checking incomming message"; 
	//log(LOG_NET);

	if (flag) {
		int buf_len = n;
		unsigned char *buffer = new unsigned char[buf_len];

		MPI_Recv(buffer, buf_len, MPI_BYTE, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status); // příjem odpovědi

		//logstream << "NETWORK got message, handling";
		//log(LOG_NET);

		//TODO tady se bude "tvarit" jinak nez pri iddle
		handleMessage(status, buffer, buf_len);
	}
}

//------------------------------------------------------------------------------

void GoDoSomeWorkBuddy(){
	int discnt = CHECK_MSG_AMOUNT; // pocet cyklu po zkontrolovani prichozich zprav
	int len,          // delka nove pripravovane permutace
	    toAdd;        // cislo, ktere se zapasovava do teto permutace (toto je vzdy len-1, je to proto, ze permutace mame od 0 do n-1)
	unsigned char *p, // Permutace, se kterou zrovna pracujeme. 
	            *old; // Permutace, zrovna vybrana ze zasobniku. 

	do { // while (!sIsEmpty())
		sPop(old, toAdd); // vezmeme prvni prvek zasobniku a jeho delku (ta se rovna cislu, ktere budeme pridavat do permutace)
		len = toAdd + 1;  // toAdd je cislo, ktere budeme vkladat do novych "podvetvi" pri rozvoji, len je delka nove vytvarenych permutaci

		if(old == NULL) { cout << "pretekl zasobkik sPop"; exit(2); }
		if(len > n)     { cout << "list na zasobniku";     exit(2); }

		logstream << "poped perm: " << permutationToString(old, toAdd) << " from stack depth:" << sIdx << " from top: " << sTop;
		log(LOG_STACK);

		for (int j = 0; j < len; j++) { // iterace pres pozice, na ktere lze cislici pridavat
			p = new unsigned char[len];
			for (int k = 0; k < len; k++) { // pridavani do pole
				if      (k < j)  p[k] = old[k];
				else if (k == j) p[k] = toAdd;
				else if (k > j)  p[k] = old[k - 1];
			}

			bool isTrivial = CheckThisPermutationForMeDude( p, len );

			if(isTrivial) {
				//EndOnTrivial(); //TODO
			}

			if (cpu_count != 1 && (discnt-=1) == 0) { // v kazdem CHECK_MSG_AMOUNTtem kroku se zkontroluji prichozi zpravy
				discnt = CHECK_MSG_AMOUNT;
				DoYoHearDaPhonaRingin();
			}
		}
		delete[] old;
	} while (!sIsEmpty());
}

//------------------------------------------------------------------------------

bool CheckForNewWork(){
	int trgt = my_rank;
	int rqcnt = 0; //ptat se vsech bylo moc
 
	while (true){
		if(workRequestResponsed){ // Ptame se na dalsi praci, pouze pokud nam prisla odpoved na prechozi dotaz a ne jina zprava.
			if(!sIsEmpty()) return true;

			trgt = (trgt - 1 + cpu_count) % cpu_count;
			if(rqcnt >= MAX_WORK_REQUESTS || trgt == my_rank) return false;

			MPI_Send(NULL, 0, MPI_BYTE, trgt, MSG_WORK_REQUEST, MPI_COMM_WORLD);
			workRequestResponsed = false;
			rqcnt++;

			logstream << "NETWORK sent: ask for work cpu: " << trgt;
			log(LOG_NET);
		} else { //XXX tady se to jinak pta, bez jakykoli brzdy porad dokola nevim jeslti je to spravne
			sleep(0.1);
		}

		// kontrola prichozich zprav predtim, nez budeme rikat o praci
		DoYoHearDaPhonaRingin();
	}
	//return false; //unreachable
}

//------------------------------------------------------------------------------

void GoodJobManGoIddleNow(){
	if(cpu_count == 1) return;

	logstream << "IIIIIIIIIIIDDDDDDDDDDDDDDDLLLLLLLLLLLLLLLLLLLLLEEEEEEEEEEEEEEEEEE";
	log(LOG_NET);

	isIddle = true;

	while(isIddle){ 
		if(my_rank == CEO_CPU) {
			if(!tokenRunning) {
				unsigned char token = TKN_CAN_FINISH;
				int next_cpu = (my_rank + 1) % cpu_count; // následující jádro
	
				MPI_Send(&token, 1, MPI_BYTE, next_cpu, MSG_TOKEN, MPI_COMM_WORLD); // pošle TOKEN 0 následujícímu jádru
	
				tokenRunning = true; //zpoustime jen jednou
	
				logstream << "NETWORK: cpu " << my_rank << " sent TOKEN!!";
				log(LOG_NET);
			}
		}

		DoYoHearDaPhonaRingin();
	}
}

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------

/**
 * Main
 */
int main(int argc, char *argv[]) {
	//  Zkontrolujeme vstupy
	if (argc != 2) { cout << "no or wrong input" << endl; return 1; }


	//  Zapneme MPI
    MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
	MPI_Comm_size(MPI_COMM_WORLD, &cpu_count);

	// Mereni casu - zacatek
	double t1, t2; // casy pocatku a konce behu
	MPI_Barrier(MPI_COMM_WORLD); // mereni casu - cekam na spusteni vsech procesu
	if (my_rank == CEO_CPU) {
		cout << "Úloha: " << argv[1] << endl;
		cout << "Počet procesorů: " << cpu_count << endl;
		t1 = MPI_Wtime(); // pocatecni cas
	}

	// Nacteme a rozelseme zadani
	LoadAndDistributeData(argv[1]);
	
	// Rozesleme/Prijmeme prvotni permutace
	CreateAndSendInitialPermutations();
	
	// Dokud dostavame praci, pracujeme
	do{
		GoDoSomeWorkBuddy();
	}while( CheckForNewWork() );
	
	// Iddle time.. tady uz se jen hlida token
	GoodJobManGoIddleNow();

	// Uklid
	if(cpu_count == 1) {
		cout << "result for CPU " << my_rank << ": " << result << endl; // vypiseme vysledek
	}
	
	// Mereni casu - konec
	//MPI_Barrier(MPI_COMM_WORLD); // mereni casu - cekam na dokonceni vypoctu
	if (my_rank == CEO_CPU) {
		t2 = MPI_Wtime(); // koncovy cas
		cout << "==== Doba běhu: " << t2 - t1 << " ====" << endl;
	}

	MPI_Finalize();

	sDel();

	for (int i = 0; i < n; i++) delete[] M[i];
	delete[] M;

	return 0;
}
